import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * 二叉树的中序遍历(非递归)
 * User: xwl
 * Date: 2023-05-22
 * Time: 23:12
 */

// 节点类
class TreeNode4 {
    int val;
    TreeNode4 left;
    TreeNode4 right;
    TreeNode4() {}
    TreeNode4(int val) { this.val = val; }
    TreeNode4(int val, TreeNode4 left, TreeNode4 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Test4 {
    public void inorder(TreeNode4 root) {
        // 讨论树为空的情况
        if (root == null) {
            return;
        }
        // 创建一个节点用来存当前节点
        TreeNode4 cur = root;
        // 创建一个栈来存放节点
        Deque<TreeNode4> stack = new ArrayDeque<>();
        // 实现
        while (cur != null || !stack.isEmpty()) {
            // 判断
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 定义一个top来表示当前弹出的元素
            TreeNode4 top = stack.pop();
            System.out.println(top.val + " ");
            cur = top.right;
        }
    }
}
